#include <bits/stdc++.h>

using namespace std;

// 课程表III
// 这里有n门不同的在线课程，按从1到n编号
// 给你一个数组courses
// 其中courses[i]=[durationi, lastDayi]表示第i门课将会持续上durationi天课
// 并且必须在不晚于lastDayi的时候完成
// 你的学期从第 1 天开始
// 且不能同时修读两门及两门以上的课程
// 返回你最多可以修读的课程数目
// 测试链接 : https://leetcode.cn/problems/course-schedule-iii/

class Solution 
{
public:
    int scheduleCourse(vector<vector<int>>& courses)
    {
        // 0 : 代价
		// 1 : 截止
        sort(courses.begin(), courses.end(), [&](const auto& a, const auto& b){
            return a[1] < b[1]; // 按照 lastDay 从小到大排序
        });

        priority_queue<int> heap; // 保存 duration 的最大值
        int time = 0; // 已消耗的时间
        for(auto& c : courses)
        {
            if(time + c[0] <= c[1])
            {
                time += c[0];
                heap.push(c[0]);
            }
            else
            {
                // time + c[0] > c[1]
                if(!heap.empty() && heap.top() > c[0]) // 该课程的时间比之前的最长时间要短
                {
                    // 由于是根据 lastDay 排序的，所以当前这么课程是一定可以学习的
                    time += c[0] - heap.top();
                    heap.pop(); // 反悔，撤销之前 duration 最长的课程，改成学习该课程
                    heap.push(c[0]);
                }
            }
        }
        return heap.size();
    }
};